1. Field of the Invention
The present invention relates to an associative memory, and in particular to have comparison function of storage of data, stored data and data input from outside.
2. Description of the Prior Art
Conventional memory reads and writes the data by means of applying address. On the contrary, associative memory can compare in parallel read and write of data, input retrieval data and the entire stored data. It is typically as comparison function of associative memory to give judgement whether retrieval data agrees with stored data or not, and also it is possible for skilled persons in prior art to judge the relationship thereof.
Such a comparison is applied when it give the judgement of which cache hit or miss hit in cache memory.
If coincidence detecting function of this associative memory is composed in use of general memory, another data comparator is required, in order to make comparison operation, data stored in memory is read once, comparison of read data and retrieval data must be made by said comparator. That is, comparison operation of associative memory has advantage which can act more high-speed than comparison operation of system which made use of memory and comparator.
Now, an associative memory in prior art will be described according to appended drawings of FIG. 6 to FIG. 8.
FIG. 6 is a general diagram of a typical Content Addressable Memory (hereinafter called CAM).
As shown in FIG. 6, numeral (1) is a buffer register which stores retrieval data (1a), numeral (2) is a CAM cell (Content Addressable Memory cell) having function which can store data and compare the data content, numeral (3) is CAM array (Content Addressable Memory array) in which the CAM cell (2) is arranged by ixj arrangement, numeral (4) is a data line communicating said retrieval data to the respective CAM cell (2), numeral (5) is a retrieval storing buffer register stored retrieved result, numeral (6) is a match line which detects compared result in the CAM cell (2) and communicates it to corresponding retrieval storage buffer register (5), numeral (7) is an entry area which composes of i-piece CAM cell (2) arranged in one direction arrangement in said CAM array (3) and is connected to the match line (6).
The said Content Addressable Memory is used in cache memory or data base and the like.
FIG. 7 is a structural example of the TAG memory applying the CAM.
Numeral (8) is a buffer register storing an input address (8a) which consists of p bit, numeral (9) is a partial buffer register storing a TAG address (9a) which composes of high order i bit of the input address (8a), numeral (10) is a partial buffer register storing an entry address (10a) which composes of low order p-i bit of the input address (8), numeral (11) is a sense amplifier which senses output level from the match line (6), numeral (12) is a transmission gate (hereinafter call T.G.) which communicates the retrieved output of the match line (6) to the sense amplifier (11), numeral (13) is entry decoder for decoding said T.G. (12) by means of said entry address (10), numeral (14) is an entry signal line connecting output of said entry decoder (13) and gate input of said T.G. (12), numeral (15) is a bit line, numeral (16) is a negative logic bit line, numeral (17) is a driver which drives potential of said data line (4) and communicates it to said bit lines (15) and (16).
Next, the operation will be explained.
As shown in FIG. 7, in view of operation of comparison time in the TAG memory, p bit data is input into the input address buffer register (8) storing the input address (8a) from outside. i bit of the buffer register (9) of the TAG address (9a) which is a part of this input address (8a) is provided for a buffer register (1) and is communicated to corresponding bit lines (15) and (16) as retrieval data to pass the data line (4) via the driver (17).
Further, in the respective CAM cell (2), comparison of the TAG address communicated with the bit lines (15) and (16) and data stored in the CAM array (3) is made at the same time. This comparison operation is made over the entire area of the CAM array (3) by means of comparison function of the CAM cell (2). In view of the respective entry area (7), if all CAM cell (2) agree, the match line (6) of said entry area (7) is level which indicates agreement, for example, Hi-level. On the contrary, if there is disagreement of a bit in one entry area (7), the match line (6) of said entry area (7) is level which indicates disagreement or for instance, Low-level.
On the other hand the entry decoder (13) is decoded by binary numbers indicated with p-i bit from the entry address buffer register (10) which is a part of the input address, the output signal enables corresponding T.G. (12) to conduct through entry signal line (14) so that the entry area (7) can be selected.
Thereby, selected level of the match line (6) is communicated to the sense amplifier (11). This sense amplifier (11) senses the level and inputs agreement or disagreement. For example, since p-bit entry address composes of five bit, when "01011" is input, the entry decoder (13) conducts eleventh-T.G. 12-11 and selects eleventh-entry 7-11. When this eleventh-entry 7-11 is agreement, it is Hi-level, when said eleventh-entry 7-11 is disagreement, it is Low-level, thereby this level, sense amplifier (11) outputs agreement or disagreement of the selected entry area (7).
As shown in FIG. 8, said CAM cell (2) composes a general random access memory (RAM) element and three transistors. For example, when "1" of Hi-level is stored in said RAM element, in case that "0" of Low-level is retrieval data is input via the bit line (15) and "1" of Hi-level is input via the bit line (16), since the transistor of connected match line connected to said match line (6); and is on, the match line (6) is Low-level which indicates disagreement.
Moreover, when said retrieval data is "1" of Hi-level, said transistor is not on, thereby the match line (6) is kept in Hi-level which indicates agreement.
As the above mentioned, in all CAM cell (2) of the entry area (7), if it agrees with "1" of retrieval data, the match line (6) is kept in Hi-level, if it disagrees with "1" of retrieval data, the match line (6) is Low-level, the retrieved result in this entry area (7) can be provided.
Since a general associative memory is composed as the above described, when it is used in cache memory and the like, if there is locality in retrieved data, all entry area (7) must be compared with retrieval data "1" as object comparing the entire CAM array (3), and further because it takes time for retrieving and operation speed delays, there are problems that consumed electric current increases.